class Solution {
public:
    string getPermutation(int n, int k) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        string ans;
        vector<int> P(n + 1);
        vector<int> numbers(n);

        for (int i = 0; i < n; ++i) {
            numbers[i] = i + 1;
        }

        P[0] = 1;
        for (int i = 1; i <= n; ++i) {
            P[i] = P[i - 1] * i;
        }
        for (int num = n; num >= 1; --num) {
            int sum = 0;
            int i = 0;
            for (; i < num; ++i) {
                if (sum + P[num - 1] >= k) {
                    break;
                }
                sum += P[num - 1];
            }
            ans += static_cast<char>(numbers[i] + '0');
            k -= sum;

            for (int j = 0, len = 0; j < num; ++j) {
                if (j != i) {
                    numbers[len++] = numbers[j];
                }
            }
            numbers.pop_back();
        }
        return ans;
    }
};
